// 1. 公共前缀-14-最大公共前缀
// 2. 移除元素-26-删除有序数组中的重复项
// 3. 移除元素-27-移除元素
// 4. 移除元素-283-移动0
// 5. 反转-7-数字反转
// 6. 反转-344-反转字符串
// 7. 反转-541-反转字符串2
// 8. 翻转字符串里的单词
// 9. 反转-189-轮转数组

// 10. 回文-125-是否是回文
// 11. 回文-5-最长回文子串
// 12. 合并-88-合并两个有序数组
// 13. 合并-4-两个正序数组的中位数
// 14. 11-盛最多水的容器

// 15. 和-15-三数之和（待理解-中等）
// 16. 和-18-四数之和（待理解-中等）






// 1. 最大公共前缀
// 题解：两个字符串的公共前缀部分
// 思路：从头循环比较每个元素是否相同，不同则返回prefix结果，相同则拼接结果
// 注意：循环结束如果没有返回还要继续返回
var longestCommonPrefix = function(strs) {
  let pre = strs[0];
  for(let i = 1; i< strs.length; i++){
      let j =0 // 放外面
      for(; j< pre.length && j< strs[i].length; j++){
          if(pre[j] !== strs[i][j]) break
      }
      pre = pre.substring(0,j)
      if(pre === '') return '' //减少递归条件
  }
  return pre
};

// 2. 删除有序列表中的重复项 set也能解决吧
// 题解：返回新列表的长度，有序数组
// 思路：指针快慢问题，没有相同替换slow与fast元素，slow++；
// 注意：结束条件当fast走到头，快慢起始不同（0,1），先++再替换，返回结果是slow+1
var removeDuplicates = (nums) => {
  let slow = 0;
  let fast = 1; // 区别于其他
  while (fast < nums.length) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
    fast++
  }
  return slow + 1
}

// 3. 移除元素
// 题解：删除目标元素，返回新列表的长度
// 思路：依旧快慢指针，循环数组长度，当慢指针所指元素值不等于目标值，替换快慢元素，slow++
// 注意：与上一题的区别，起始相同；先替换，再++；返回slow
var removeElement = (nums, val) => {
  let slow = 0;
  let fast = 0;
  while (fast < nums.length) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast]
      slow++;  // 区别重复，先改值再+
    }
    fast++
  }
  return slow //slow 移动后所在位置已经不包含在区间内相当于+1的长度
}

// 4.移动0
// 题解：0都移动到最后
// 思路：同上一题，删除目标元素
// 注意：返回的是原数组
var removeZero = (nums) => {
  let slow = 0;
  let fast = 0;
  while (fast < nums.length) {
    if (nums[fast] !== 0) {
      [nums[fast], nums[slow]] = [nums[slow], nums[fast]]
      slow++;
    }
    fast++
  }
  return nums
}
console.log(removeZero([0, 1, 23, 0, 11, 0]))


// 5.数字反转
// 题解：将一个数字反转
// 思路：通过取余的方式倒叙处理，整数部分继续；余*10
// 注意：边界条件判断 2的31次方和-2的31次方 1. Math.floor(-0.1) = -1 2. 边界范围 
var reverseNums = (x) => {
  let res = 0;
    let num = Math.abs(x)
    while(num !== 0){
        let dig = num % 10
        num = Math.floor(num / 10)
        res = res* 10 + dig
        // 边界条件判断
        if (res < Math.pow(-2, 31) || res > Math.pow(2, 31) - 1) {
            return 0
        }
    }
    return x > 0 ? res : res * -1
}
console.log(reverseNums(-123))

// 6.反转字符串
// 题解：将一个字符串反转
// 思路：循环，两边夹逼，替换
// 注意：长度/2 可优化循环
var reverseString = (str) => {
  let len = str.length;
  for (let i = 0; i < (len / 2); i++) {
    [str[i], str[len - i - 1]] = [str[len - i - 1], str[i]]
  }
  return str;
}
console.log(reverseString(["h", "e", "l", "l", "o"]))

// 7.反转字符串2
// 题解：翻转2k个的前k个
// 思路：for循环嵌套while，自增是2*k
// 注意：右边界要和字符串长度比较
var reverseString2 = (str, k) => {
  let arr = Array.from(str);
  for (let i = 0; i < str.length; i += 2 * k) { // 0 --> 4
    let left = i;
    let right = Math.min(i + k, str.length) - 1; // 担心越界
    while (left < right) {
      // 判断当前
      [arr[left], arr[right]] = [arr[right], arr[left]]; // 区域内反转
      left++;
      right--;
    }
  }
  return arr.join('')
}
console.log(reverseString2(s = "abcdefg", k = 2))

// 8.翻转字符串里的单词
// 题解：翻转字符串里的单词
// 思路：分割，翻转，再拼接
// 注意：非最优解
var reverseWords = (str) => {
  return str.trim().split(/\s+/).reverse().join(' ')
}
console.log(reverseWords('ab cd '))

// 9.轮转数组
// 题解：将一个字符串，在k位置，两个字符串分别反转
// 思路：先整体反转，再分别反转前面与后面
// 注意：k是长度
var rotate = function(nums, k) {
    k=k%nums.length; // 重要
    reverse(nums,0,nums.length-1);
    reverse(nums,0,k-1);
    reverse(nums,k,nums.length-1);
};
function reverse(arr,start,end){
    while(start<end){
        var temp=arr[start];
        arr[start]=arr[end];
        arr[end]=temp;
        start++;
        end--; 
    }
}


// 10.回文-是否是回文
// 题解：判断一个串是否是回文
// 思路：两边夹逼，对比
// 注意：无
var isPalindrome = (s) => {
  // 替换 /[^a-zA-Z0-9]/g 所有非字母和数字，/\s/g 所有空格为""，然后统一转为大写或者小写。
  s=s.replace(/[^a-zA-Z0-9]/g,"").replace(/\s/g,"").toLowerCase();
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left++] !== s[right--]) {
      return false
    }
  }
  return true
}
console.log(isPalindrome('aba'))

// 11.回文-最长回文子串（连续）
// 题解：寻找这个串中最长的回文子串
// 思路：中心扩散的方式，存一个最长的串
// 注意：区分基数扩散，与偶数扩散
var longestPalindrome = (s) => {
  let res = '';
  for (let i = 0; i < s.length; i++) {
    helper(i, i); // 基数扩散
    helper(i, i + 1); // 偶数扩散
  }

  function helper(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
      const maxStr = s.slice(l + 1, r) // 拿到回文字符， 注意 上面while满足条件后多执行了一次，所以需要l+1, r+1-1
      if (maxStr.length > res.length) res = maxStr;
    }

  }
  return res
}
console.log(longestPalindrome("aaaaab"))

// 12.合并两个有序数组
// 题解：将两个有序数组合并
// 思路：都是从后往前添加，谁大就取谁，相应的索引减少
// 注意：直接操作数组1，循环数组2
var combinArr = (arr1, m, arr2, n) => {
  let l1 = m - 1;
  let l2 = n - 1;
  let l = m + n - 1;
  while (l2 >= 0) {
    // if (l1 < 0) {
    //   arr1[l--] = arr2[l2--]
    // }
    arr1[l--] = (arr1[l1] > arr2[l2]) ? arr1[l1--] : arr2[l2--]
  }
  return arr1;
}
console.log(combinArr([1, 4, 6, 0, 0, 0], 3, [2, 3, 5], 3))

// 13.合并 两个有序数组的中位数
// 题解：两个有序数组的中位数
// 思路：首先合并两个有序数组，然后判读基数还是偶数取中间索引
// 注意：qu'fen
var findMedianSortArr = (nums1, nums2) => {
  var res = [];
  while (num1.length && nums2.length) {
    if (num1[0] < num2[0]) {
      res.push(num1.shift())
    } else {
      res.push(num2.shift())
    }
  }
  res = res.concat(num1, num2); // 处理未处理完的
  
  let median
  if (res.length % 2) { // 基数
    median = res[Math.floor(res.length / 2)];
  } else { // 偶数两个求和
    let len = res.length / 2
    median = (res[len - 1] + res[len]) / 2
  }
  return median
}
console.log(findMedianSortArr(nums1 = [1, 2], nums2 = [3]))


// 14.盛水最多的容器 带一点贪心的意思
// 题解：选中两条线后，中间的都可以不看
// 思路：两边夹逼，谁小谁从中间移动，面积(right - left + 1) * minHeight; 
// 注意：取最低高度
var maxArea = (height) => {
  let left = 0;
  let right = height.length - 1;
  let max = 0;
  while (left < right) {
    // // left, right小的那个先向内移动，     如果高的指针先移动，那肯定不能使当前面积更大，移动小的还有可能变高
    const minHeight = height[left] < height[right] ? height[left++] : height[right--];
    const area = (right - left) * minHeight; 
    max = Math.max(max, area)
  }
  return max
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))



// 15.三数之和
// 题解：三个数之和为0，的所有可能
// 思路：确定一个点，然后小了就扩大左边界，大了就要缩小右边界
// 注意：去重 第一层i与i-1；二层l与l+1，r与r-1；当前数字大于0则和一定大于0 可剪枝，因为已经排序
var threeSum = function(nums) {
  nums.sort((a,b) => a-b)
  let res = []
  if(nums === null || nums.length < 3) return res
  
  for(let i =0 ; i< nums.length; i++){
      if(nums[i] > 0) break
      if(i > 0 && nums[i] == nums[i-1]) continue; // 去重

      let l = i+1;
      let r = nums.length -1;

      while(l < r){
          let sum = nums[i] + nums[l] + nums[r]
          if(sum < 0) {l++; continue };
          if(sum > 0) {r--; continue };
          res.push([nums[i], nums[l], nums[r]])
          while(l < r && nums[l] === nums[l+1]) l++;
          while(l < r && nums[r] === nums[r-1]) r--;
          l++
          r--
      }
  }

  return res

};

// 16.四数之和
// 题解：四个数之和为target
// 思路：和三数之和相比多了一层循环
// 注意：原来大于0break 剪枝不需要；循环需要留出其他元素的位置
var fourSum = function(nums, target) {
  nums.sort((a,b) => a - b)
  let res = []
  if(nums === null || nums.length < 4) return res

  for(let i =0; i< nums.length-3; i++){
      if(i> 0 && nums[i] === nums[i-1]) continue

      for(let j =i+1; j <nums.length-2; j++){
          if(j> i+1 && nums[j] === nums[j-1]) continue

          let l = j+1;
          let r = nums.length -1


          while(l< r){
              let sum = nums[i]+ nums[j] + nums[l] + nums[r];
              if(sum < target) { l++; continue};
              if(sum > target) { r--; continue};
              res.push([nums[i], nums[j], nums[l], nums[r]])
              while(l< r && nums[l]=== nums[l+1]) l++;
              while(l < r && nums[r] === nums[r-1]) r--;
              l++;
              r--;
          }
      }
  }
  return res
};








